package astar
{
	import flash.geom.Point;
	import flash.utils.getTimer;

	public class Astar
	{
        private var openList:Array;//开放列表
        private var closedList:Array;//封闭列表
        private var grid:AstarGrid;

		private var startNode:AstarNode;//起点
        private var endNode:AstarNode;//终点

        private var straightCost:Number=1.0; //直线代价        
        private var diagCost:Number=Math.SQRT2; //对角线代价
		private var isEight:Boolean = false;


		/**
		 * A*寻路 
		 * @param arr  障碍列表
		 * @param row 地图行
		 * @param col  地图列
		 * 
		 */		
		public function Astar(row:int, col:int)
		{
			grid = new AstarGrid(row, col);
		}

		
		public function findPath(star:Point, end:Point):Boolean
		{
			openList = new Array();
			closedList = new Array();
			
			startNode= grid.getNode(star.x, star.y);
			endNode= grid.getNode(end.x, end.y);
			endNode.parent = null;
			
			startNode.g=0;
			startNode.h=euclidian(startNode);
			startNode.f=startNode.g + startNode.h;
			
			return search();
		}
		
		public function search():Boolean
		{
			var node:AstarNode= startNode;
			
			while (node != endNode)
			{
				//找出相邻节点的x,y范围
				var startX:int=Math.max(0, node.x - 1);
				var endX:int=Math.min(grid.numRows - 1, node.x + 1);
				var startY:int=Math.max(0, node.y - 1);
				var endY:int=Math.min(grid.numCols - 1, node.y + 1); 
				//循环处理所有相邻节点
				for (var i:int=startX; i <= endX; i++)
				{
					for (var j:int=startY; j <= endY; j++)
					{
						var test:AstarNode=grid.getNode(i, j);
						
						if(!nodeIsOk(node, test))
							continue;
						
						var cost:Number=straightCost;                      
						//如果是对象线，则使用对角代价
						if (!((node.x == test.x) || (node.y == test.y)))
						{
							cost=diagCost;
						}  
						
						//计算test节点的总代价                      
						var g:Number=node.g + cost;
						var h:Number=euclidian(test);                      
						var f:Number=g + h;  
						
						//如果该点在m_arrOpen或close列表中
						if (isOpen(test) || isClosed(test))
						{
							//如果本次计算的代价更小，则以本次计算为准
							if (f<test.f)
							{                          
								test.f=f;
								test.g=g;
								test.h=h;
								test.parent=node;//重新指定该点的父节点为本轮计算中心点
							}
						}
						else//如果还不在m_arrOpen列表中，则除了更新代价以及设置父节点，还要加入m_arrOpen数组
						{
							test.f=f;
							test.g=g;
							test.h=h;
							test.parent=node;
							openList.push(test);
						}
					}
				}
				//把处理过的本轮中心节点加入close节点
				closedList.push(node);
				if (openList.length == 0)
				{
					trace("没找到最佳节点，无路可走!");
					return false
				}
				//按总代价从小到大排序
				openList.sortOn("f", Array.NUMERIC);
				//从m_arrOpen数组中删除代价最小的结节，同时把该节点赋值为node，做为下次的中心点
				node=openList.shift() as AstarNode;
			}
			return true;
		}

		/**
		 *  判断节点是否可通行 
		 * @param a
		 * @param b
		 * @return 
		 * 
		 */		
		private function nodeIsOk(a:AstarNode, b:AstarNode):Boolean
		{
			
			if (b == a || b.walkable == 1 || grid.getNode(a.x, b.y).walkable == 1 || grid.getNode(b.x, a.y).walkable == 1)
				return false;
			
			if(!isEight && a.x != b.x && a.y != b.y)
				return false;
			
			return true;
		}
		
		//曼哈顿估价法
		private function manhattan(node:AstarNode):Number
		{
			return Math.abs(node.x - endNode.x) + Math.abs(node.y - endNode.y);
		}
		
		//几何估价法
		private function euclidian(node:AstarNode):Number
		{
			var dx:Number=node.x - endNode.x;
			var dy:Number=node.y - endNode.y;
			return Math.sqrt(dx * dx + dy * dy);
		}
		
		//对角线估价法
		private function diagonal(node:AstarNode):Number
		{
			var dx:Number=Math.abs(node.x - endNode.x);
			var dy:Number=Math.abs(node.y - endNode.y);
			var diag:Number=Math.min(dx, dy);
			var straight:Number=dx + dy;
			return diag + (straight - 2 * diag);
		}
		
		private function getNode(x:int, y:int):AstarNode
		{
			return grid.getNode(x, y);
		}
		
		/**
		 * 判断节点是否开放列表 
		 * @param node
		 * @return 
		 * 
		 */		
		private function isOpen(node:AstarNode):Boolean
		{
			var i:int = openList.indexOf(node);
			
			return i != -1 ? true : false;
		}
		
		/**
		 * 判断节点是否封闭列表 
		 * @param node
		 * @return 
		 * 
		 */		
		private function isClosed(node:AstarNode):Boolean
		{
			var i:int = closedList.indexOf(node);
			
			return i != -1 ? true : false;
		}
		
		
		
		public function getPath():Array
		{
			var arrPath:Array =new Array();
			if(!endNode || !endNode.parent) return arrPath;
			
			var node:AstarNode=endNode;
			arrPath.push(new Point(node.x, node.y));
			while (node != startNode)
			{
				node=node.parent;
				arrPath.unshift(new Point(node.x,node.y));
			}
			return arrPath;
		}
		
		public function isWalkable(x:int, y:int):Boolean
		{
			var node:AstarNode = getNode(x, y);
			
			if(node && !node.walkable)
				return true;
			
			return false;
		}
		
		public function setWalkable(x:int, y:int, value:int):void
		{
			grid.setWalkable(x, y, value);
		}
	}
}